package 程序员面试金典;

import java.util.Arrays;

public class 马戏团人塔 {
    public int bestSeqAtIndex(int[] height, int[] weight) {
        int len=height.length;
        int[][] person = new int[len][2];
        for (int i = 0; i < len; i++) {
            person[i]=new int[]{height[i],weight[i]};
        }
        //身高升序排序，如果相同，体重降序
        Arrays.sort(person,(a,b)-> a[0]==b[0]?b[1]-a[1]:a[0]-b[0]);
        int res=0;
        int[] dp = new int[len];
        for (int[] ints : person) {
            int i = Arrays.binarySearch(dp, 0, res, ints[1]);
            if (i<0)
                i=-(i+1);
            dp[i]=ints[1];
            if (i==res)
                res++;
        }
        return res;
    }
}
